1. Field of Invention
The present invention pertains broadly to a system for recording or storing the positions of a plurality of objects arranged in an essentially two-dimensional array or plat. The invention more especially pertains to an improved system for generating graphical displays of typically rectangular objects arranged on an essentially two-dimensional surface. The invention has particular application to a graphical system for storing, displaying and manipulating the positions of substantially two-dimensional objects such as the elements of integrated circuits, printed circuit boards, and the like.
2. Description of Related Art
One of the first steps in manufacturing a circuit such as an integrated circuit or printed circuit board involves positioning, or "laying out", the various elements of the circuit and their interconnections. Typically, these circuit elements include transistors, resistors, capacitors, wires, and the like.
Various computer-based systems, called "graphical data structures", have been used to lay out these types of circuits. These graphical data structures typically include routines capable of storing the circuit elements in computer memory, adding new elements, deleting or re-arranging existing elements, and conducting regional queries of elements. When the circuit elements have been finally laid out, information regarding their positioning is output from the computer memory and used to create one or more sheets or "tapes," which provide a blueprint-like representation of the circuit. Later, the tapes may be used in the process of etching, depositing, or otherwise constructing the integrated circuit on a silicon substrate, such processes being well known in the art of semiconductor manufacturing.
The function of graphical data structures is not limited to manipulating circuit elements; in fact, graphical data structures are generally useful in manipulating other two-dimensional shapes. The two-dimensional shapes stored in a graphical data structure are called "objects".
Graphical data structures come in a variety of forms. One known graphical data structure is the multi-dimensional binary tree, often called the "k-d tree". With k-d trees, the size of an object is considered to be the size of the smallest rectangle ("bounding rectangle") capable of containing the object. Objects are sorted according to the horizontal and vertical ("x-y") positions of the left, right, top, and bottom sides of their bounding rectangle.
FIG. 1A shows several objects to be stored in a k-d tree and FIG. 1B illustrates the structure of the k-d tree after the objects are stored therein. Generally, objects to be stored in a k-d tree are sorted according to the position of their edges. In successive sorting operations, the edges are sorted in an order such as the following: left edge, bottom edge, right edge, and top edge.
In the example of FIGS. 1A and 1B, seven objects are to be stored in the k-d tree. Sorting the objects of FIG. 1A according to their left edges places objects 51, 52, and 56 to the left of the left edge of object 53, and objects 54, 55, and 57 to the right of the left edge of object 53. Object 53 is chosen as a central reference point, or "node" of the rectangles, since half of the objects' left edges are to the left of the left edge of object 53 and half of the objects' left edges are to the right of the left edge of object 53.
After the objects are divided in this manner, they are sorted according to the position of their bottom edges. For instance, object 51 forms a node since the bottom edge of object 51 is between the bottom edges of objects 52 and 56. Similarly, object 54 forms a node since the bottom edge of object 54 is between the bottom edges of objects 57 and 55. If additional objects were present in the structure, the objects would be sorted by their right, and then their top edges. This process would be repeated until each node contains a single object.
By using this method, time is saved since a particular region can be queried without searching through all data in the k-d tree. In the above example, a query of the left region would yield objects 53, 51, 52, and 56.
Although k-d trees have been useful for some purposes, they suffer from a number of disadvantages. In the above example, the right region would become more densely populated than the left region if several objects having bounding rectangles with left-edge positions to the right of object 53 were inserted. In this condition, the k-d tree is "unbalanced", and queries of the k-d tree are inefficient. As a result, when the right region is queried, the query must search through more than half of all objects in the k-d tree. In the extreme case, when all objects in the left region are deleted, the k-d tree degenerates into a simple linked list (described below), and queries of the right region must search through all objects in the k-d tree.
An unbalanced k-d tree is inefficient since it requires excessive time to conduct queries. One approach that has been used to overcome balancing problems is periodically re-balancing the k-d tree. Re-balancing involves selecting a new node to re-define the left and right regions. Thus, after re-balancing, each region contains about half of the total number of objects, with the node dividing the two regions.
Although some of the problems with k-d trees are reduced by re-balancing, k-d trees are still limited since they require more computer memory than might be desired for some purposes. Some tolerate this limitation, since k-d trees can offer high query speed in some applications.
Another known graphical data structure is the "quad tree". This category includes a group of programs that have certain common characteristics. With quad trees, a horizontal line and a vertical line divide a two-dimensional area into four quadrants. Objects are categorized according to whether they lie entirely within one of the quadrants, intersect the vertical line, or intersect the horizontal line. For greater detail, each quadrant can be divided into sub-quadrants.
Like other graphical data structures of this type, the object of a query is to identify objects lying within a specified query region. One disadvantage of querying using quad trees is that the queries often yield duplicate results. Since it is possible for an object spanning the query region to intersect the horizontal and/or vertical lines, every query must search through all objects intersecting the vertical and/or horizontal lines.
One modification used to overcome this disadvantage has been to abandon the categories based on horizontal and vertical line intersection. Thus, an object is categorized solely upon the quadrant or sub-quadrant that the object lies in. However, if an object spans two or more quadrants, a query including those quadrants would encounter the object two or more times, i.e. once in each quadrant.
One solution to duplicate reporting in quad trees has been to maintain a software flag for each object. After the object has been reported during a query, a flag associated with that object is set. When an object's flag is set during a query, that object cannot be reported for the remainder of the query. As a result, objects are never reported more than once.
Although this solution has been helpful in some applications, it is limited in that it requires additional computer memory to operate. Furthermore, this solution is limited since it slows the query process by requiring additional operations, such as re-setting the flags. Generally, quad trees are not as memory-intensive as k-d trees. Nonetheless, quad trees require more memory than might be desired in some applications.
Another popular graphical data structure is the linked list. A typical linked list involves a list of data records, wherein each record contains an object and a pointer that points to the beginning of the next record. Although linked lists are useful for some purposes, they are not as efficient as k-d trees or quad trees. As a result, linked lists might be unsatisfactory for certain applications, since linked lists require additional time to conduct queries, additions, and deletions.
One common disadvantage of the k-d trees, quad trees, and linked lists is that they tend to be inefficient when the graphical data include objects having diverse ratios of vertical dimension to horizontal dimension ("aspect ratios"). Quad trees, k-d trees, and linked lists may be satisfactory in some applications involving small objects; however, k-d trees, quad trees, and linked lists perform poorly when applied to the graphical handling of objects of various sizes, e.g., small objects, long narrow objects, medium-sized objects, and very large objects. This type of application is representative of a typical VLSI (very large scale integrated) chip layout. Thus, k-d trees, quad trees, and linked lists perform poorly when the graphical data comprises a VLSI chip layout.